Cellular phones, no more than a curiosity less than a decade ago, are now commonplace. In addition to their wide spread use in developed counties, cellular phones are popular in developing countries as well, where wireless telecommunications systems for supporting such cellular service can be implemented much more quickly than a conventional wireline system.
The acceptance and growth of wireless systems for data communications, as opposed to voice communications, has been relatively slow. It is believed, however, that such wireless data communications systems are ready for significant growth. Factors portending such growth include the ever-decreasing size of computers and the increasing regularity with which such computers are fitted with receivers for receiving wireless signals. Such small size and wireless capabilities facilitates mobile access to data networks, such as the Internet. See, Hills, "Terrestial Wireless Networks," vol. 278, no. 4, Scientific American, pp. 86-88, (April 1998).
Designers of wireless data networks will face certain challenges in making information readily accessible to mobile clients. One problem relates to the efficient retrieval of desired information by the client Such a problem is inherent in an "asymmetric" communication environment, such as a data communications network. A communication environment is described as "asymmetric" if the available or required communication capacity from the information source ("server") to the information recipient ("clients") is much larger than that available or required in the reverse direction.
FIG. 1 depicts an example of such an asymmetric environment wherein numerous mobile clients, five of which are pictured as mobile clients 104a-104e, retrieve information from a server base station 102 that broadcasts such information over a wireless channel. Mobile clients 104a-104e may be, for example, lap-top computers that include a receiver for receiving wireless communications. In the present example, such computers are assumed to be running on batteries, as may be required, for example, if the computer is in the possession of a user travelling in an automobile.
There are two fundamental models by which clients can retrieve information from a server. One is the "pull-based" model, used in traditional client-server information-retrieval systems, wherein multiple clients retrieve information by making individual requests to the server. Such a model is poorly suited for the asymmetric environment under consideration. First, since each "terminal" (i.e., client) is assumed to be a weak transmitter, a variety of signal strength/interference problems may arise. Secondly, an enormous volume of requests would be received by the server, making the processing of such requests problematic.
A second model is the "push-based" model, wherein the server broadcasts its information over a communication medium to multiple clients who receive such information simultaneously (ignoring time delays). Each of such clients then actively retrieves information of interest from the universe of information received. While the "push-based" model is effective in disseminating massive amounts of information to numerous clients, such an approach has associated with it potentially significant shortcomings.
In particular, an individual client looking for certain items of information may have to actively listen to the communication medium for a long time to receive such information. The "cost" to a client of information retrieval may be viewed as comprising two distinct components: (1) the time elapsed in retrieving information of interest, and (2) the time elapsed in actively listening to the communications medium for the information of interest. The first component is referred to as the "access time" and the second component is referred to as the "tuning time." The distinction between access time and tuning time is based on an assumption that the clients are able to switch between a resource-consuming (e.g, battery power) "active mode" and a resource-conserving "sleep mode." Such modes are commonly used in computers.
Listening to the communications medium requires that a client be in the active mode. To decrease time spent in the active mode, a server may provide information indicative of when various items of information will be broadcast ("indexing information"). Thus, knowing that for at least a certain period of time no relevant information will be broadcast, the client is able to lapse into the resource-conserving sleep mode. Tuning time thus forms a measure of the efficient utilization of certain important resources, such as the limited power supply of mobile lap-top computers, in the process of information retrieval.
A substantial amount of work in the prior art has addressed the issue of minimizing access time in the classical pull-based model. There is a fundamental difference, however, between efficient information retrieval in pull-based models and in push-based models. In particular, in the pull-based model, an information search can always begin at a certain well-defined location, such as the "root" of a "balanced search tree," for example. In a push-based broadcast model, the client begins its information search based only on the information that is being broadcast at the moment it tunes in. This aspect of the push-based broadcast model makes the problem of minimizing access and tuning time particularly difficult
The prior art has addressed the issue of information retrieval in push-based broadcast models, but mainly towards the end of minimizing access time, not tuning time, and typically in models in which the broadcast consists solely of data items, not indexing information. Information retrieval in an indexed data broadcast was first addressed by lmielinsli et al. in "Energy Efficient Indexing on Air," Proc. ACM SIGMOD Conf., May 1994. lmielinski et al. considered a simple case where the distribution over data items is uniform (i.e., each data item appears the same number of times as all other data items in the broadcast).
It would be desirable then, to have a broadcasting method that seeks to minimize a client's expected access time ("mean access time") and expected tuning time ("mean tuning time"), and for an information repository comprising arbitrarily distributed data items.